package MyUtils;

import 其他.DataStructure.ListNode;
import 其他.DataStructure.TreeNode;

import java.util.*;

public class MHUtils{

    /*
        a~b随机整数
    */
    public static void suiji_atob(int a,int b){
        int start=a;
        int end=b;
        int iRandom = (int)(start+Math.random()*(end-start));
        System.out.println(iRandom);
    }

    /*
        造链表test用的例子
        1 2 3 4
    */
    public static ListNode lizi_lianbiao(String s){
        String[] ss = s.split(" ");
        ListNode dm = new ListNode(-1);
        ListNode dmt = dm;
        for (int i = 0; i < ss.length; i++) {
            ListNode cur = new ListNode(Integer.parseInt(ss[i]));
            dm.next = cur;
            dm = dm.next;
        }
        return dmt.next;
    }
    public static void ptLianBiao(ListNode h){
        while (h!=null){
            System.out.print(h.val+" ");
            h=h.next;
        }
    }

    /*
        层序 每层一个tmp
    */
    public static List<List<Integer>> cengxu(TreeNode root) {
        if(root==null){
//            return null;
            //返回结果为String可以直接“”
            //但如果是List<>,空时要return new
            return new ArrayList<>();
        }
        List<List<Integer>> res = new ArrayList<>();
        //初始rot放入32,看图
        List<Integer> rotTmp  = new ArrayList<>();
        rotTmp.add(root.val);
//        res.add(new ArrayList<>(root.val));
        res.add(rotTmp);

        //自己不放心
        if(root.left==null && root.right==null){
            return res;
        }
        Queue<TreeNode> que = new LinkedList<>();
        if(root.left!=null) {
            que.add(root.left);
        }
        if(root.right!=null){
            que.add(root.right);
        }
        int oldSize = que.size();
        while(oldSize > 0){
            List<Integer> tmp = new ArrayList<>();
            for (int i = 0; i < oldSize; i++) {
                TreeNode poll = que.poll();
                //看图,这里少了
                tmp.add(poll.val);
                //可能有跳跃null，不是完全二叉
                if(poll==null){
                    //resstr不打印东西
                }else{
                    if(poll.left!=null){
                        que.add(poll.left);
                    }
                    if(poll.right!=null){
                        que.add(poll.right);
                    }
                }
            }
            //后退一级记录oldSize,因为要一整行完事
            oldSize = que.size();
            res.add(tmp);
        }

        return res;
    }




    public static int[][] scopeListToShuZu(List<int[]> list){
        int n = list.size();
        int[][] res = new int[n][2];
        for (int i = 0; i < n; i++) {
            res[i][0] = list.get(i)[0];
            res[i][1] = list.get(i)[1];
        }
        return res;
    }
    public static void ptListByHead(ListNode head){
        while(head != null){
            System.out.print(head + " ");
        }
        System.out.println();
    }

    /*
        最长 递增 子序长度
     */
    public static int zuichang_dizeng_length(int[] nums){
        int[] dp = new int[nums.length];
        dp[0]=1;
        for (int i = 1; i < nums.length; i++) {
            int max = -1;
            for (int l = 0; l <= i-1 ; l++) {
                if(nums[i]>nums[l]) {
                    max = Math.max(dp[l], max);
                }
            }
            //别忘+1本身 / 没有比当前i小的->设为1
            dp[i] = max==-1?
                    1:max+1;
        }
        //res不是[n-1],需要遍历拿到max
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < dp.length; i++) {
            max = Math.max(dp[i],max);
        }
        return max;
    }
    /*
        最长 公共 子序长度
     */
    public static int zuichang_gonggong_length(String t1, String t2) {
        char[] s1 = t1.toCharArray(), s2 = t2.toCharArray();
        int n1 = s1.length, n2 = s2.length;
        int[][] dp = new int[n1][n2];
        //由下方初始化j-1,致这里要单独先初始化
        dp[0][0] = s1[0]==s2[0]?1:0;
        for (int j = 1; j < dp[0].length; j++) {
            dp[0][j] = s1[0]==s2[j]?
                    //dp[0][j-1]+1:
                    1:
                    dp[0][j-1];
        }
        for (int i = 1; i < dp.length; i++) {
            dp[i][0] = s1[i]==s2[0]?
                    1:
                    dp[i-1][0];
        }
        //从1走
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length ; j++) {
                //相同:res长度+1 (因为是子序直接无限加,不用像串要考虑可能扔掉前面
                if(s1[i]==s2[j]){
                    //为什么不考虑(i-1,j)? 因为我就拿个数而已,又不牵扯改动(i-1,j)
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                //不同：取1次大的吧（注意我只要最终[n][m]所以这个max只取1次
                else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        //因为是”前“,可以用mn
        return dp[n1-1][n2-1];
    }



    public static void ptIntShuzu_one(int[] p){
        System.out.println(Arrays.toString(p));
    }
    public static void ptIntShuzu(int[][] p){
        for (int i = 0; i < p.length; i++) {
            for (int j = 0; j < p[0].length; j++) {
                System.out.print(p[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println("——————————————————————————");
    }
    public static void ptCharShuzu(char[][] p){
        for (int i = 0; i < p.length; i++) {
            for (int j = 0; j < p[0].length; j++) {
                System.out.print(p[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println("——————————————————————————");
    }

    public static String treeToStr(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        sb.append(root.val + ",");
        while (!q.isEmpty()) {
            TreeNode cur = q.poll();
            if (cur.left != null) {
                q.add(cur.left);
                sb.append(cur.left.val + ",");
            } else if (cur.left == null) {
                sb.append("null,");
            }

            if (cur.right != null) {
                q.add(cur.right);
                sb.append(cur.right.val + ",");
            } else if (cur.right == null) {
                sb.append("null,");
            }
        }
        return sb.toString();
    }
    public static TreeNode strToTree(String data) {
        String[] s = data.split(",");
        TreeNode headRoot = new TreeNode(Integer.parseInt(s[0]));
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(headRoot);
        int curInd = 0;
        int step = 0;
        while (!q.isEmpty()) {
            int oldSize = q.size();
            for (int i = 0; i < oldSize; i++) {
                TreeNode cur = q.poll();
                int curIndTmp = curInd;
                if (cur == null) {
                    continue;
                }
                if (curIndTmp + 1 < s.length) {
                    if (s[curIndTmp + 1].equals("null")) {
                        cur.left = null;
                        q.add(null);
                    } else {
                        cur.left = new TreeNode(Integer.parseInt(s[curIndTmp + 1]));
                        q.add(cur.left);
                    }
                    curInd++;
                }
                if (curIndTmp + 2 < s.length) {
                    if (s[curIndTmp + 2].equals("null")) {
                        cur.right = null;
                        q.add(null);
                    } else {
                        cur.right = new TreeNode(Integer.parseInt(s[curIndTmp + 2]));
                        q.add(cur.right);
                    }
                    curInd++;
                }
            }
            step++;
        }
        return headRoot;
    }

    // pt递归 - 调试
    public static void debug_digui(int konggeNum, String str){
        for (int i = 0; i < konggeNum; i++) {
            System.out.print("|   ");
        }
        System.out.println(str);
    }
    // -> 新版
    /*
    用法：严格按代码中的变量名是啥 自己就format打一样的
     */
    static int e = 0;
    public static void can(String str){
        for (int i = 0; i < e; i++) {
            System.out.print("|   ");
        }
        System.out.println(str);
        e++;
    }
    public static void r(String str){
        --e;
        for (int i = 0; i < e; i++) {
            System.out.print("|   ");
        }
        System.out.println("return " + str);
    }
    public static void cur(String str){
        --e;
        for (int i = 0; i < e; i++) {
            System.out.print("|   ");
        }
        System.out.println("| " + str);
        e++;
    }


    /*
        pt调试-while

       【用法】
            w(){
               w(i) 1

               cw() 3 自定义

               nw(i) 2 复制1 前补n
            }
            空行 = w(!)
    */
    /*
       【例子】
            while (right < s.length()) {
                //w
                w(String.format("r=%s", right));

                char curRight = s.charAt(right);
                right++;

                //cw
                cw(String.format("set=%s", right));

                charNumberMap.put(curRight, charNumberMap.getOrDefault(curRight, 0) + 1);
                while (isContainsAndCharNumBigThanAllT(charNumberMap, t)){
                    w2(String.format("l=%s",left));
                    if( right - left <= resMinLen ) {
                        resMinLen = right - left;
                        resMinStr = s.substring(left, right);
                    }
                    char curLeft = s.charAt(left);
                    charNumberMap.put(curLeft, charNumberMap.get(curLeft) - 1);
                    left++;
                    cw2(String.format("c2=%s", left));
                    while (left < s.length() && !tCharSet.contains(s.charAt(left))) {
                        w3(String.format("l=%s", left));
                        left ++;
                        cw3(String.format("cur3=%s", left));
                        nw3(String.format("l=%s", left));
                    }
                    nw2(String.format("l=%s",left));
                }

                //nw
                nw(String.format("r=%s", right));
            }
     */
    //w
    public static void w(String s){
        System.out.println(s);
    }
    public static void cw(String s){
        System.out.println("| "+s);
    }
    public static void nw(String s){
        System.out.println("next"+s);
        System.out.println("");
    }
    //w2
    public static void w2(String s){
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 1; i++) {
            sb.append("|  ");
        }
        sb.append(s);
        System.out.println(sb.toString());
    }
    public static void cw2(String s){
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 1; i++) {
            sb.append("|  ");
        }
        sb.append("| ");sb.append(s);
        System.out.println(sb.toString());
    }
    public static void nw2(String s){
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 1; i++) {
            sb.append("|  ");
        }
        sb.append(s);
        //补空挡
        sb = new StringBuilder();
        for (int i = 0; i < 1; i++) {
            sb.append("|  ");
        }
        sb.append("next");
        System.out.println(sb+s);
        System.out.println("|  ");
    }
    //w3
    public static void w3(String s){
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 2; i++) {
            sb.append("|  ");
        }
        sb.append(s);
        System.out.println(sb.toString());
    }
    public static void cw3(String s){
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 2; i++) {
            sb.append("|  ");
        }
        sb.append("| ");sb.append(s);
        System.out.println(sb.toString());
    }
    public static void nw3(String s){
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 2; i++) {
            sb.append("|  ");
        }
        sb.append(s);
        //补空挡
        sb = new StringBuilder();
        for (int i = 0; i < 2; i++) {
            sb.append("|  ");
        }
        sb.append("next");
        System.out.println(sb+s);
        System.out.println("|  |  ");
    }




    /*
        min3
     */
    public static int min3(int a, int b, int c){
        int min1 = Math.min(a, b);
        int min2 = Math.min(c,min1);
        return min2;
    }
    public static int max3(int a,int b,int c){
        int a1 = Math.max(a, b);
        return Math.max(a1, c);
    }
    public static int max4(int a,int b,int c, int d){
        int a1 = Math.max(a, b);
        int c1 = Math.max(a1, c);
        return Math.max(d,c1);
    }
    public static int max5(int a,int b,int c, int d,int e){
        int a1 = Math.max(a, b);
        int c1 = Math.max(a1, c);
        int d1 = Math.max(d,c1);
        return Math.max(d1,e);
    }
    /*
        (String/Interge)数组 to list

        用时 不用标T
        -> .var 自动识别出来T
     */
    public static <T> List<T> shuzuToList(T[] nums){
        List<T> list = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            list.add(nums[i]);
        }
        return list;
    }

    /*
     int[] 放入List
     */
    public static List<Integer> shuzuToList(int[] p){
        List<Integer> tmp = new ArrayList<>();
        for (int i : p) {
            tmp.add(i);
        }
        return tmp;
    }


    /*
        二分找一个数的下标
        注：有重复时，要用左右边界模板
     */
    public static int erfen_findOnlyOne(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else if(nums[mid] == target) {
                return mid;
            }
        }
        return -1;
    }

    /*
        反转数组
    */
    public static int[] reverse_shuzu(int[] p){
        Stack<Integer> stack = new Stack<>();
        for (int coin : p) {
            stack.push(coin);
        }
        int[] rever_coins = new int[p.length];
        int i =0;
        while(!stack.isEmpty()){
            rever_coins[i++] = stack.pop();
        }
        return rever_coins;
    }
}
